package problems.solved;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

public class Problem14A {
	private static final long TARGET = 1000000;

	private static final int CACHE_SIZE = 30000; // more or less optimal, 7 sec...
	private static Map<Long, List<Long>> cache = new HashMap<Long, List<Long>>(CACHE_SIZE);

	public static void main(String[] args) {
		List<Long> sequence = new ArrayList<Long>();

		for (long i = 1; i < TARGET; i++) {
			List<Long> list = new ArrayList<Long>((int) (i/10000)); 
			addSequence(i, list);
			
			if (list.size() > sequence.size()) {
				sequence = list;
			}
		}
		
		System.out.printf("Longest sequence has size %d (%d unique): %s%n", sequence.size(), new HashSet<Long>(sequence).size(), sequence);
	}

	private static void addSequence(long i, List<Long> list) {
		if (cache.containsKey(i)) {
			list.addAll(cache.get(i));
			return;
		}
		list.add(i);
		if (i > 1) {
			addSequence(process(i), list);
		}
		if (i < CACHE_SIZE) {
			final ArrayList<Long> toCache = new ArrayList<Long>(list.subList(list.indexOf(i), list.size()));
			System.out.println(i + ": " + toCache);
			cache.put(i, toCache);
		}
	}
	
	private static long process(long n) {
		return n % 2 == 0 ? n/2 : 3*n + 1;
	}
}
